// @algorithm @lc id=37 lang=cpp 
// @title sudoku-solver


#define print(...)
// @test([["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]])=[["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]
// @test([[".",".","9","7","4","8",".",".","."],["7",".",".",".",".",".",".",".","."],[".","2",".","1",".","9",".",".","."],[".",".","7",".",".",".","2","4","."],[".","6","4",".","1",".","5","9","."],[".","9","8",".",".",".","3",".","."],[".",".",".","8",".","3",".","2","."],[".",".",".",".",".",".",".",".","6"],[".",".",".","2","7","5","9",".","."]])=[["5","1","9","7","4","8","6","3","2"],["7","8","3","6","5","2","4","1","9"],["4","2","6","1","3","9","8","7","5"],["3","5","7","9","8","6","2","4","1"],["2","6","4","3","1","7","5","9","8"],["1","9","8","5","2","4","3","6","7"],["9","7","5","8","6","3","1","2","4"],["8","3","2","4","9","1","7","5","6"],["6","4","1","2","7","5","9","8","3"]]
#define BOX(i,j)        box[(i)/3*3+(j)/3]
#define FLIP(i,j,bit)   row[i] ^= 1<<(bit),\
                        col[j] ^= 1<<(bit),\
                        BOX((i),(j)) ^= 1<<(bit)
#define CHOICES(i,j)    ( (~(BOX((i),(j)) | row[i] | col[j])) & 0x1FF )
#define COUNT(m)        __builtin_popcount(m)
#define LAST(m)         __builtin_ctz((m) & (-(m)))
using blank_t = pair<int,int>;
using iterator_t = vector<blank_t>::iterator;
class Solution {
public:
    void solveSudoku(vector<vector<char>>& board) {
        int row[9]={0}, col[9]={0}, box[9]={0};
        vector<blank_t> blanks;
        print("orginal:\n")
        print(Mat(board))
        for(int i=0; i<board.size(); i++){
            for(int j=0; j<board[i].size(); j++){
                if(board[i][j] != '.'){
                    FLIP(i,j, board[i][j]-'1');
                    continue;
                }
                auto choices = CHOICES(i,j);
                if(choices&(choices-1)){ // 去掉最后一个1，还有其他1(方案)
                    blanks.emplace_back(i,j);
                    continue;
                }
                // 只有一种可能的直接填上
                auto bit = LAST(choices);
                FLIP(i, j, bit);
                board[i][j] = '1' + bit;
            }
        }
        print(std::hex, Array(row), "\n", Array(col), "\n", Array(box), "\n")
        print("prepared:\n")
        print(Mat(board))

        auto chooseBlank = [&]()->pair<int,int>{
            int minChoices = 10, r=-1, c=-1;
            for(auto & [i,j] : blanks){
                if(board[i][j] != '.') continue;
                int choices = CHOICES(i,j);
                int n = COUNT(choices);
                if(n < minChoices){
                    minChoices = n;
                    r = i, c = j;
                }
                if(minChoices == 1) break;
            }
            return {r,c};
        };

        bool solved = false;
        function<void()> dfs = [&](){
            auto blk = chooseBlank();
            if(blk.first<0 || blk.second<0){
                solved = true;
                return;
            }
            for(auto choices = CHOICES(blk.first, blk.second);
                choices && !solved; choices = choices&(choices-1)){
                auto bit = LAST(choices);
                FLIP(blk.first, blk.second, bit);
                board[blk.first][blk.second] = '1' + bit;
                dfs();
                if(solved) break;
                FLIP(blk.first, blk.second, bit);
                board[blk.first][blk.second] = '.';
            }
        };
        dfs();
        print("solved=", solved, "\n")
        print(Mat(board))
        print("-----------\n")
        print(std::hex, Array(row), "\n", Array(col), "\n", Array(box), "\n")
    }
};